//package work.rightAnswer;
//
//import work.ListNode;
//
//class Solution_148 {
//    public ListNode sortList(ListNode head) {
//        //排序链表：归并排序
//        //归并排序的本质是将无序列表拆分为子列表，直到子列表为有序，然后左右两个有序生成一个总体有序
//        //终止条件：子列表
//        if(head==null||head.next==null){
//            return head;
//        }
//
//        //找到中间节点
//        //快慢节点初始化设置，从链表的哨兵头节点（无意义头节点），迈出第一步的位置
//        ListNode slow = head;
//        ListNode fast = head.next;
//        while (fast!=null&&fast.next!=null){
//            slow = slow.next;
//            fast = fast.next.next;
//        }
//
//        //slow为中间节点,断开连接
//        ListNode tmp = slow.next;
//        slow.next = null;
//        ListNode left = sortList(head);
//        ListNode right = sortList(tmp);
//        ListNode pre = new ListNode();
//        ListNode t = pre;
//        while (left!=null&&right!=null){
//            if(left.val<=right.val){
//                t.next = left;
//                left = left.next;
//            }else {
//                t.next = right;
//                right = right.next;
//            }
//            t = t.next;
//        }
//
//        t.next = left==null ? right:left;
//        return pre.next;
//
//    }
//}